{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Replacements to Sort the Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumReplacement"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #将数组排序的最少替换次数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始的整数数组&nbsp;<code>nums</code>&nbsp;。每次操作中，你可以将数组中任何一个元素替换为&nbsp;<strong>任意两个</strong>&nbsp;和为该元素的数字。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>比方说，<code>nums = [5,6,7]</code>&nbsp;。一次操作中，我们可以将&nbsp;<code>nums[1]</code> 替换成&nbsp;<code>2</code> 和&nbsp;<code>4</code>&nbsp;，将&nbsp;<code>nums</code>&nbsp;转变成&nbsp;<code>[5,2,4,7]</code>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你执行上述操作，将数组变成元素按 <strong>非递减</strong> 顺序排列的数组，并返回所需的最少操作次数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [3,9,3]\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>以下是将数组变成非递减顺序的步骤：\n",
    "- [3,9,3] ，将9 变成 3 和 6 ，得到数组 [3,3,6,3] \n",
    "- [3,3,6,3] ，将 6 变成 3 和 3 ，得到数组 [3,3,3,3,3] \n",
    "总共需要 2 步将数组变成非递减有序，所以我们返回 2 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [1,2,3,4,5]\n",
    "<b>输出：</b>0\n",
    "<b>解释：</b>数组已经是非递减顺序，所以我们返回 0 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-replacements-to-sort-the-array](https://leetcode.cn/problems/minimum-replacements-to-sort-the-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-replacements-to-sort-the-array](https://leetcode.cn/problems/minimum-replacements-to-sort-the-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,9,3]', '[1,2,3,4,5]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumReplacement(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        curMax = nums[len(nums) - 1]\n",
    "        for i in range(len(nums) - 2, -1, -1):\n",
    "            if nums[i] > curMax:\n",
    "                if nums[i] % curMax == 0:\n",
    "                    ans += nums[i] // curMax - 1\n",
    "                else:\n",
    "                    cnt = nums[i] // curMax + 1\n",
    "                    ans += cnt - 1\n",
    "                    curMax = nums[i] // cnt\n",
    "            else:\n",
    "                curMax = nums[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumReplacement(self, nums: List[int]) -> int:\n",
    "        ans=0\n",
    "        for i in range(1,len(nums)):\n",
    "            if nums[-i]<nums[-i-1]:\n",
    "                ans+=int(nums[-i-1]/nums[-i]+0.99999)-1\n",
    "                nums[-i-1]=nums[-i-1]//int(nums[-i-1]/nums[-i]+0.99999)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumReplacement(self, nums: List[int]) -> int:\n",
    "        ans=0\n",
    "        for i in range(1,len(nums)):\n",
    "            if nums[-i]<nums[-i-1]:\n",
    "                ans+=int(nums[-i-1]/nums[-i]+0.999)-1\n",
    "                nums[-i-1]=nums[-i-1]//int(nums[-i-1]/nums[-i]+0.999)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumReplacement(self, nums: List[int]) -> int:\n",
    "        ans=0\n",
    "        for i in range(1,len(nums)):\n",
    "            if nums[-i]<nums[-i-1]:\n",
    "                t=int(nums[-i-1]/nums[-i]+0.999)\n",
    "                ans+=t-1\n",
    "                nums[-i-1]=nums[-i-1]//t\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumReplacement(self, nums: List[int]) -> int:\n",
    "        ans=0\n",
    "        for i in range(1,len(nums)):\n",
    "            if nums[-i]<nums[-i-1]:\n",
    "                t=ceil(nums[-i-1]/nums[-i])\n",
    "                ans+=t-1\n",
    "                nums[-i-1]=nums[-i-1]//t\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumReplacement(self, nums: List[int]) -> int:\n",
    "        def fun(n,r):\n",
    "            return [n//int(n/r+0.99999),int(n/r+0.99999)-1]\n",
    "        ans=0\n",
    "        for i in range(1,len(nums)):\n",
    "            if nums[-i]<nums[-i-1]:\n",
    "                t=fun(nums[-i-1],nums[-i])\n",
    "                nums[-i-1]=t[0]\n",
    "                ans+=t[1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumReplacement(self, nums: List[int]) -> int:\n",
    "        ans=0\n",
    "        for i in range(1,len(nums)):\n",
    "            if nums[-i]<nums[-i-1]:\n",
    "                t=floor(nums[-i-1]/nums[-i]+0.999)\n",
    "                ans+=t-1\n",
    "                nums[-i-1]=nums[-i-1]//t\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumReplacement(self, nums: List[int]) -> int:\n",
    "        ans=0\n",
    "        for i in range(1,len(nums)):\n",
    "            if nums[-i]<nums[-i-1]:\n",
    "                ans+=int(nums[-i-1]/nums[-i]+0.999)-1\n",
    "                nums[-i-1]=nums[-i-1]//int(nums[-i-1]/nums[-i]+0.999)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumReplacement(self, nums: List[int]) -> int:\n",
    "        retVal = 0\n",
    "\n",
    "        numsSize = len(nums)\n",
    "        for i in range(numsSize - 2, -1, -1):\n",
    "            if nums[i] <= nums[i + 1]:\n",
    "                continue\n",
    "\n",
    "            operations = (nums[i] + nums[i + 1] - 1) // nums[i + 1]\n",
    "            retVal += (operations - 1)\n",
    "            nums[i] = nums[i] // operations\n",
    "\n",
    "        return retVal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumReplacement(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            k = (nums[i] - 1) // nums[i + 1] + 1\n",
    "            nums[i] = nums[i] // k\n",
    "            ans += k - 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumReplacement(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        prev = inf\n",
    "        for cur in nums[::-1]:\n",
    "            n = 1\n",
    "            if cur > prev:\n",
    "                n = ceil(cur / prev)\n",
    "                ans += n - 1\n",
    "            prev = cur // n            \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumReplacement(self, nums: List[int]) -> int:\n",
    "        ans,t=0,nums[-1]\n",
    "        for i in nums[-2::-1]:\n",
    "            ans+=(i-1)//t\n",
    "            t=i//((i-1)//t+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumReplacement(self, nums: List[int]) -> int:\n",
    "        operations = 0\n",
    "        prev_bound = nums[-1]\n",
    "\n",
    "        for num in reversed(nums[:-1]):\n",
    "            no_of_times = (num + prev_bound - 1) // prev_bound\n",
    "            operations += no_of_times - 1\n",
    "            prev_bound = num // no_of_times\n",
    "            \n",
    "        return operations"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "\n",
    "# start-----------------------------------------------------\n",
    "class Solution:\n",
    "    def minimumReplacement(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        pre = inf\n",
    "        n = len(nums)\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if nums[i] <= pre:\n",
    "                pre = nums[i]\n",
    "            else:\n",
    "                if nums[i] % pre == 0:\n",
    "                    ans += nums[i] // pre - 1\n",
    "                else:\n",
    "                    l,r = 1, pre\n",
    "                    while l < r:\n",
    "                        m = (l + r + 1) >> 1\n",
    "                        cnt = nums[i] // m\n",
    "                        les = nums[i] % m\n",
    "                        if (pre - m) * cnt >= les:\n",
    "                            l = m\n",
    "                        else:\n",
    "                            r = m - 1\n",
    "                    ans += nums[i] // pre \n",
    "                    pre = l\n",
    "                    \n",
    "        return ans\n",
    "s = Solution()\n",
    "s.minimumReplacement([1,13,15,2,5,14,12,17])\n",
    "# end-------------------------------------------------------"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumReplacement(self, nums: List[int]) -> int:\n",
    "        ans,last=0,nums[-1]\n",
    "        for x in nums[-2::-1]:\n",
    "            if x<=last: last=x\n",
    "            else:\n",
    "                q,r=x//last,x%last\n",
    "                if r==0: ans+=q-1\n",
    "                else:\n",
    "                    ans+=q\n",
    "                    last=x//(q+1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumReplacement(self, nums: List[int]) -> int:\n",
    "        ## m 为拆分出的数的最小值，初始化为最后一个数字\n",
    "        ## 倒序遍历\n",
    "        m = nums[-1]\n",
    "        k = 0\n",
    "        for n in nums[::-1]:\n",
    "            x = math.ceil(n/m)\n",
    "            k += x - 1\n",
    "            m = math.floor(n / x)\n",
    "        return k\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumReplacement(self, nums: List[int]) -> int:\n",
    "        ## m 为拆分出的数的最小值，初始化为最后一个数字\n",
    "        ## 倒序遍历\n",
    "        m = nums[-1]\n",
    "        k = 0\n",
    "        for n in nums[::-1]:\n",
    "            x = math.ceil(n/m)\n",
    "            k += x - 1\n",
    "            m = int(n / x)\n",
    "        return k\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumReplacement(self, nums: List[int]) -> int:\n",
    "        ans,last=0,nums[-1]\n",
    "        for x in nums[-2::-1]:\n",
    "            if x<=last: last=x\n",
    "            else:\n",
    "                q,r=x//last,x%last\n",
    "                if r==0: ans+=q-1\n",
    "                else:\n",
    "                    ans+=q\n",
    "                    last=math.floor((last*q+r)/(q+1))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minimumReplacement(self, nums: List[int]) -> int:\r\n",
    "        \"\"\"\r\n",
    "        Greedy\r\n",
    "        1. 拆分後只能讓數字變小，不能變大，所以最後一個數字一定是拆分後的最大值\r\n",
    "        2. 從後往前遍歷，每次拆分都是讓最大值變小，直到小於當前的最小值m\r\n",
    "        3. 假設拆分出x個數字，所以nums[i] <= mx，而拆分次數為k = x -1\r\n",
    "           舉例來說，nums[i] = 10, m = 3，則x = 4，拆分後為[3,3,2,2]，k = 3\r\n",
    "        4. x >= ceil(nums[i] / m)，為使x最小取等號，x = ceil(nums[i] / m)\r\n",
    "           k = x - 1 = ceil(nums[i] / m) - 1 = (nums[i] - 1) // m \r\n",
    "        5. 為了使拆分後的數字盡可能的大，拆分出的最小數字m = floor(nums[i] / x)\r\n",
    "        \"\"\"\r\n",
    "        # 拆分\r\n",
    "        ans, m = 0, nums[-1]\r\n",
    "        for num in reversed(nums):\r\n",
    "            k = math.ceil(num / m) - 1\r\n",
    "            ans += k\r\n",
    "            m = num // (k + 1)\r\n",
    "        return ans\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumReplacement(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        bound = nums[-1]\n",
    "        ans = 0\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if nums[i] <= bound:\n",
    "                bound = nums[i]\n",
    "                continue\n",
    "            else:\n",
    "                m = nums[i]//bound\n",
    "                r = nums[i]%bound\n",
    "                if r == 0:\n",
    "                    ans += m - 1\n",
    "                else:\n",
    "                    ans += m\n",
    "                    bound = nums[i]//(m+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumReplacement(self, nums: List[int]) -> int:\n",
    "        nums_len = len(nums)\n",
    "        if nums_len == 1:\n",
    "            return 0\n",
    "        m = nums[-1]\n",
    "        res = 0\n",
    "        for i in range(nums_len - 2, -1, -1):\n",
    "            cnt = (nums[i] - 1) // m\n",
    "            res += cnt\n",
    "            m = nums[i] // (cnt + 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumReplacement(self, nums: List[int]) -> int:\n",
    "        ans, m = 0, nums[-1]\n",
    "        for num in reversed(nums):\n",
    "            k  = (num - 1) // m \n",
    "            ans += k\n",
    "            m = num // (k + 1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumReplacement(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        upper = nums[-1]\n",
    "        opt = 0\n",
    "\n",
    "        for i in range(n-1, -1, -1):\n",
    "            t = nums[i]\n",
    "            k = (t-1)//upper\n",
    "            opt += k\n",
    "            upper = t//(k+1)\n",
    "\n",
    "        return opt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumReplacement(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        last = nums[-1]\n",
    "        res = 0\n",
    "        for num in nums[:-1][::-1]:\n",
    "            if num < last:\n",
    "                last = num \n",
    "            else:\n",
    "                k = (num - 1) // last + 1 \n",
    "                res += k - 1 \n",
    "                last = num // k \n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumReplacement(self, nums: List[int]) -> int:\n",
    "        ans, last = 0, nums[-1]\n",
    "        for i in range(len(nums)-2, -1, -1):\n",
    "            if nums[i]>last:\n",
    "                div = (nums[i]-1)//last+1\n",
    "                last = floor(nums[i]/div)\n",
    "                ans += div-1\n",
    "            else:\n",
    "                last = nums[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumReplacement(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        m = nums[-1]\n",
    "        res = 0\n",
    "        for i in range(n - 1):\n",
    "            k = nums[n - i - 2]\n",
    "            if k > m:\n",
    "                p = (k-1) // m\n",
    "                m = k // (p + 1)\n",
    "                res += p\n",
    "            else:\n",
    "                m = k\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumReplacement(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        bound = nums[-1]\n",
    "        ans = 0\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if nums[i] <= bound:\n",
    "                bound = nums[i]\n",
    "                continue\n",
    "            else:\n",
    "                m = nums[i]//bound\n",
    "                r = nums[i]%bound\n",
    "                if r == 0:\n",
    "                    ans += m - 1\n",
    "                else:\n",
    "                    ans += m\n",
    "                    bound = max(nums[i]//(m+1), (bound+r)//2)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumReplacement(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        god = nums[-1]\n",
    "        res = 0\n",
    "        for i in range(n-2, -1, -1):\n",
    "            if god >= nums[i]:\n",
    "                god = nums[i]\n",
    "            else:\n",
    "                temp = ceil(nums[i] / god)\n",
    "                res += temp-1\n",
    "                god = nums[i] // temp\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumReplacement(self, nums: List[int]) -> int:   \n",
    "        #copy 0x3\n",
    "        ans,m= 0,nums[-1]\n",
    "        for num in reversed(nums):\n",
    "            k = (num-1)//m\n",
    "            ans += k\n",
    "            m = num//(k+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumReplacement(self, nums: List[int]) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "        mx = nums[-1]\n",
    "        ans = 0\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            if nums[i] > mx:\n",
    "                k = (nums[i] + mx - 1) // mx\n",
    "                ans += k - 1\n",
    "                mx = nums[i] // k\n",
    "            else:\n",
    "                mx = nums[i]\n",
    "            # print(i, mx)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumReplacement(self, nums: List[int]) -> int:\n",
    "        ans,m=0,nums[-1]\n",
    "        for num in reversed(nums):\n",
    "            k=(num+m-1)//m #需要操作多少次\n",
    "            k-=1\n",
    "            ans+=k\n",
    "            m=num//(k+1)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumReplacement(self, nums: List[int]) -> int:\n",
    "        ans, cur_min = 0, nums[-1]\n",
    "        for num in reversed(nums):\n",
    "            op_num = (num - 1) // cur_min\n",
    "            ans += op_num\n",
    "            cur_min = num // (op_num + 1)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumReplacement(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        pre = nums[-1]\n",
    "        n = len(nums)\n",
    "        for i in range(n-2, -1, -1) :\n",
    "            if nums[i] > pre :\n",
    "                k = ceil(nums[i] / pre)\n",
    "                ans += (k-1)\n",
    "                pre = nums[i] // k\n",
    "            else :\n",
    "                pre = nums[i]\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumReplacement(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        prev = nums[n-1]\n",
    "        res = 0\n",
    "        for i in range(n-2, -1, -1):\n",
    "            num = nums[i]\n",
    "            k = ceil(num / prev)\n",
    "            res += k - 1\n",
    "            prev = num // k\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumReplacement(self, nums: List[int]) -> int:\n",
    "        res, cur_min = 0, nums[-1]\n",
    "        for num in reversed(nums):\n",
    "            op_num = (num - 1) // cur_min\n",
    "            res += op_num\n",
    "            cur_min = num // (op_num + 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumReplacement(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        m = nums[-1]\n",
    "        for n in reversed(nums):\n",
    "            k = (n - 1) // m\n",
    "            ans += k\n",
    "            m = n // (k + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumReplacement(self, nums: List[int]) -> int:\n",
    "        ans, last = 0, nums[-1]\n",
    "        for i in range(len(nums) - 2, -1, -1):\n",
    "            if nums[i] > last:\n",
    "                k = (nums[i] - 1) // last + 1\n",
    "                last = nums[i] // k\n",
    "                ans += k-1\n",
    "            else:\n",
    "                last = nums[i]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumReplacement(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        nextMin = nums[-1]\n",
    "        for i in range(len(nums) - 2, -1, -1):\n",
    "            if nums[i] <= nextMin:\n",
    "                nextMin = nums[i]\n",
    "            else:\n",
    "                res += (nums[i] - 1) // nextMin\n",
    "                nextMin = nums[i] // ((nums[i] - 1) // nextMin + 1)\n",
    "        return res                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumReplacement(self, nums: List[int]) -> int:\n",
    "        ans, m = 0, nums[-1]\n",
    "        for num in reversed(nums):\n",
    "            k = (num - 1) // m\n",
    "            ans += k\n",
    "            m = num // (k + 1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumReplacement(self, nums: List[int]) -> int:\n",
    "        count = 0\n",
    "        n = len(nums)\n",
    "        nex = nums[-1]\n",
    "        for i in range(len(nums) - 2, -1, -1):  # 从倒数第二个数字开始遍历 进行比较\n",
    "            k = (nums[i] - 1) // nex + 1 \n",
    "            count += k - 1\n",
    "            nex = nums[i] // k\n",
    "        return count\n",
    "\n",
    "\n",
    "                    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumReplacement(self, nums: List[int]) -> int:\n",
    "        last = float('inf')\n",
    "        res = 0\n",
    "        for n in reversed(nums):\n",
    "            if n > last:\n",
    "                parts = (n + last - 1) // last\n",
    "                last = n // parts\n",
    "                res += parts - 1\n",
    "                # last = l\n",
    "            else:\n",
    "                last = n\n",
    "        return res\n",
    "        # (last-1+1)*x\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumReplacement(self, nums: List[int]) -> int:\n",
    "        ans, m = 0, nums[-1]\n",
    "        for num in reversed(nums):\n",
    "            k = (num - 1) // m\n",
    "            ans += k\n",
    "            m = num // (k + 1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumReplacement(self, nums: List[int]) -> int:\n",
    "        l = len(nums)\n",
    "        res = 0\n",
    "        bound = nums[-1]\n",
    "        for i in range(l - 2, -1, -1):\n",
    "            if nums[i] > bound:\n",
    "                replacement, new_bound = self.break_num(nums[i], bound)\n",
    "                res += replacement\n",
    "                bound = min(bound, new_bound)\n",
    "            else:\n",
    "                bound = min(bound, nums[i])\n",
    "        \n",
    "        return res\n",
    "\n",
    "    def break_num(self, num: int, bound: int) -> tuple[int, int]:\n",
    "        # If num is already less than or equal to bound, no replacement is needed\n",
    "        if num <= bound:\n",
    "            return (0, num)\n",
    "        \n",
    "        count = num // bound if num % bound == 0 else num // bound + 1\n",
    "        \n",
    "        # Calculate the new bound, which is the largest number that can be used to replace\n",
    "        # parts of num without exceeding the original bound\n",
    "        new_bound = num // count\n",
    "        \n",
    "        return (count - 1, new_bound)\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumReplacement(self, nums: List[int]) -> int:\n",
    "        ans, m = 0, nums[-1]  # 初始化结果 ans 和初始的 m 值为最后一个数\n",
    "        for num in reversed(nums):  # 从后往前遍历数组中的每个数\n",
    "            k = (num - 1) // m  # 计算当前数 num 需要重复的次数，以使其不超过 m\n",
    "            ans += k  # 将重复次数 k 加到结果 ans 中\n",
    "            m = num // (k + 1)  # 更新 m 的值，使其为下一个数需要重复的最大次数\n",
    "        return ans  # 返回最终的结果 ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumReplacement(self, nums: List[int]) -> int:\n",
    "        l = len(nums)\n",
    "        res = 0\n",
    "        bound = nums[-1]\n",
    "        for i in range(l - 2, -1, -1):\n",
    "            if nums[i] > bound:\n",
    "                replacement, new_bound = self.break_num(nums[i], bound)\n",
    "                res += replacement\n",
    "                bound = min(bound, new_bound)\n",
    "            else:\n",
    "                bound = min(bound, nums[i])\n",
    "        \n",
    "        return res\n",
    "\n",
    "    def break_num(self, num: int, bound: int) -> tuple[int, int]:\n",
    "        # If num is already less than or equal to bound, no replacement is needed\n",
    "        if num <= bound:\n",
    "            return (0, num)\n",
    "        \n",
    "        # Calculate the number of replacements needed\n",
    "        replacement = (num - 1) // bound\n",
    "        \n",
    "        # Calculate the new bound, which is the largest number that can be used to replace\n",
    "        # parts of num without exceeding the original bound\n",
    "        new_bound = num // (replacement + 1)\n",
    "        \n",
    "        return (replacement, new_bound)\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumReplacement(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        post = nums[-1]\n",
    "        for i in range(n-2, -1, -1):\n",
    "            x = nums[i]\n",
    "            if x <= post:\n",
    "                post = x\n",
    "            else:\n",
    "                k = math.ceil(x/post)\n",
    "                ans += k-1\n",
    "                post= x//k\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumReplacement(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        m = nums[-1]\n",
    "        for n in reversed(nums):\n",
    "            k = (n-1)//m\n",
    "            ans += k\n",
    "            m = n//(k+1)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minimumReplacement(self, nums: List[int]) -> int:\r\n",
    "        ans, m = 0, nums[-1]\r\n",
    "        for num in reversed(nums):\r\n",
    "            k = (num - 1) // m\r\n",
    "            ans += k\r\n",
    "            m = num // (k + 1)\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumReplacement(self, nums: List[int]) -> int:\n",
    "        nums.reverse()\n",
    "        counter = 0\n",
    "        temp = nums[0]\n",
    "        for i in range(1, len(nums)):\n",
    "            tempp = (nums[i] - 1) // temp\n",
    "            counter += tempp\n",
    "            temp = nums[i] // (tempp + 1)\n",
    "\n",
    "        return counter\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumReplacement(self, nums: List[int]) -> int:\n",
    "        # 6 6 6 7 8\n",
    "        # a b -> a // (a // b)\n",
    "        ans = 0\n",
    "        cur_end = nums[-1]\n",
    "        for i in range(len(nums) - 2, -1, -1):\n",
    "            cut = nums[i] // cur_end - (nums[i] % cur_end == 0)\n",
    "            ans += cut\n",
    "            cur_end = nums[i] // (cut + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumReplacement(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        m = nums[-1]\n",
    "        for n in reversed(nums):\n",
    "            k = (n-1)//m\n",
    "            ans += k\n",
    "            m = n//(k+1)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
